home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / The World of Computer Software.iso / pccts.zip / begtut.ms next >
Text File  |  1992-12-08  |  38KB  |  1,154 lines
  1. .de iH
  2. \\$1 \\$2 \\$3 \\$4 \\$5 \\$6 \\$7 \\$8
  3. \\.XS
  4. .if \\n(NS-4     
  5. .if \\n(NS-3     
  6. .if \\n(NS-2     
  7. .if \\n(NS-1     
  8. \\*(SN \\$1 \\$2 \\$3 \\$4 \\$5 \\$6 \\$7 \\$8
  9. \\.XE
  10. ..
  11. .de 1s
  12. .nr PS 12
  13. .nr VS 13
  14. .br
  15. .LP
  16. ..
  17. .de 2s
  18. .nr PS 12
  19. .nr VS 16
  20. .br
  21. .LP
  22. ..
  23. .de cB
  24. .nr PS 10
  25. .nr VS 11
  26. .br
  27. .LP
  28. .KS
  29. .LD
  30. .ft CW
  31. ..
  32. .de cE
  33. .DE
  34. .KE
  35. .2s
  36. .ft R
  37. ..
  38. .EH 'PCCTS Introductory Tutorial 1.0x'
  39. .OH 'PCCTS Introductory Tutorial 1.0x'
  40. .EF '''Page %'
  41. .OF '''Page %'
  42. .ds d $
  43. .EQ
  44. delim $$
  45. .EN
  46. .TL
  47. \s+4Introductory Tutorial
  48. .sp 2
  49. .br
  50. PCCTS 1.0x\s-4
  51. .AU
  52. Terence Parr, Hank Dietz, Will Cohen
  53. .AI
  54. School of Electrical Engineering
  55. Purdue University
  56. West Lafayette, IN  47907
  57. \fIFall 1992\fP
  58. .sp 1
  59. \f(CWparrt@ecn.purdue.edu\fP
  60. \f(CWhankd@ecn.purdue.edu\fP
  61. \f(CWcohenw@ecn.purdue.edu\fP
  62. .2s
  63. .LP
  64. .br
  65. .QP
  66. The Purdue Compiler-Construction Tool Set (PCCTS) is a set of public
  67. domain software tools designed to facilitate the implementation of
  68. compilers and other translation systems.  In many ways, PCCTS is
  69. similar to a highly integrated version of YACC and LEX; where ANTLR
  70. (ANother Tool for Language Recognition) corresponds to YACC and DLG
  71. (DFA-based Lexical analyzer Generator) functions like LEX.  However,
  72. PCCTS has many additional features which make it easier to use for a
  73. wide range of translation problems.
  74. .QP
  75. This document introduces the basic functionality of PCCTS by example.
  76. The user need not be familiar with parsing theory or other compiler tools,
  77. but any familiarity reduces the learning curve substantially.  The PCCTS
  78. reference manual is a necessary supplement to this tutorial as information
  79. here regarding PCCTS structures and operation is incomplete.
  80. .LP
  81. .bp
  82. .NH
  83. .iH Introduction
  84. .PP
  85. PCCTS allows the user to describe languages (e.g. programming language,
  86. OS shell, game, editor); from such a description, a C program is generated that
  87. recognizes and, optionally, translates phrases in that language.
  88. The user must specify the following:
  89. .IP \fI(i)\fP
  90. How the input stream is to be broken up into lexemes (tokens) which
  91. comprise the vocabulary of the language.
  92. .IP \fI(ii)\fP
  93. How the tokens are to be grouped; i.e. what structure/grammar is to be
  94. applied to the token stream.
  95. .IP \fI(iii)\fP
  96. C actions which perform a user-specified translation.  Along with
  97. this specification, the user must also describe token attributes\(emobjects
  98. that actions use to communicate with the lexical analysis phase of translation.
  99. .LP
  100. Similarly, this tutorial is broken up into sections on lexical
  101. analysis, syntactic analysis, and actions/translation.
  102. .NH
  103. .iH Lexical Analysis
  104. .PP
  105. Before understanding a phrase in English, one must separate the stream
  106. of characters into a stream of words; e.g. the phrase: \*Qthisisveryhardtoread\*U
  107. accentuates this fact\(emrecognition cannot easily be done from a character
  108. stream, only from word/token streams.
  109. .PP
  110. Compilers and other translators are very strict about this
  111. \*Qtokenization\*U and generally describe tokens via \fIregular
  112. expressions\fR\(emexpressions that describe sets of character
  113. sequences.  The regular expressions are, in fact, language
  114. descriptions as well.  For example, \f(CWhello\fR is a regular
  115. expression that recognizes a sequence of five characters; namely, the
  116. word: \*Qhello\*U.  To inform PCCTS that \*Qhello\*U is to be a word
  117. in the vocabulary of your language, the following description would be
  118. placed in your grammar file.
  119. .cB
  120. #token LABEL "hello"
  121. .cE
  122. .LP
  123. where \f(CWLABEL\fR is some label (C \f(CW#define\fP) that you want
  124. associated with that token.  To test regular expressions in PCCTS, let
  125. us form a simple, complete description which recognizes \*Qhello\*U
  126. (we will use this description as a base for all examples in this
  127. section):
  128. .cB
  129. #header <<#include "charbuf.h">>
  130.  
  131. <<main() { ANTLR(a(), stdin); }>>
  132.  
  133. #token WORD "hello"
  134.  
  135. a : WORD ;
  136. .cE
  137. .LP
  138. This is a minimal description in that it contains everything needed
  139. for PCCTS to generate an executable (actually, to generate all C files
  140. needed for the C compiler to generate an executable).  The
  141. \f(CW#header <<...>>\fP instruction informs PCCTS that the C code inside the
  142. \f(CW<<...>>\fP action is necessary to define attributes and to
  143. compile the actions found elsewhere; for this section, we will ignore
  144. its significance.  The second action gives a main program that
  145. specifies where C is to begin execution.  It contains one statement
  146. which asks ANTLR to begin parsing at rule \f(CWa\fP.  The third
  147. instruction defines a token \f(CWhello\fP.  The fourth component of
  148. this description is a rule definition.  Rules definitions have the
  149. form:
  150. .cB
  151. \fIrule\fP: $alternative sub 1$ | $alternative sub 2$ | ... | $alternative sub n$ ;
  152. .cE
  153. .LP
  154. where each alternative is a sequence of grammatical structures that
  155. are to be matched\(emone of possible structures is a simple token
  156. reference (\f(CWWORD\fP, in our case).  Therefore, rule \f(CWa\fP
  157. says, \*Qmatch the token identified as \f(CWWORD\fP on the input
  158. stream\*U.  The C function generated for rule \f(CWa\fP asks the
  159. lexical analyzer, generated by PCCTS, to collect characters until it
  160. sees a complete token.  Each token in the vocabulary is given a unique
  161. number which the lexical analyzer returns to indicate what token was
  162. just matched.  Function \f(CWa()\fP then verifies that the number
  163. associated with \f(CWWORD\fP is indeed returned by the lexical
  164. analyzer.
  165. .PP
  166. The above example can be tested via the following sequence of commands:
  167. .cB
  168. antlr -gk t.g
  169. dlg -i parser.dlg scan.c
  170. cc -I../h -o t t.c scan.c err.c
  171. .cE
  172. The first command generates the parser, \f(CWt.c\fP, the lexical
  173. description, \f(CWparser.dlg\fP, and a support file, \f(CWerr.c\fP.
  174. The second command converts the lexical description to a C file that
  175. constitutes our scanner (lexical analyzer).  The third command
  176. compiles all C files needed to generate the executable (the
  177. \f(CW-I../h\fP option tells the C compiler where to look for the
  178. standard PCCTS include files; you will have to change this to where
  179. the PCCTS include files are located).  The output on our UNIX system
  180. looks like this (assuming the example is in file \f(CWt.g\fP):
  181. .cB
  182. % antlr -gk t.g
  183. Antlr parser generator   Version 1.06   1989-1992
  184. % dlg -i parser.dlg scan.c
  185. dlg  Version 1.0   1989, 1990, 1991
  186. % cc -I../h -o t t.c scan.c err.c
  187. .cE
  188. .LP
  189. To test the grammar file, run the executable:
  190. .cB
  191. % t
  192. hello
  193. % 
  194. .cE
  195. .LP
  196. No error message is generated and \f(CWt\fP terminates successfully.
  197. If a token not in the vocabulary of our language is typed, an error
  198. message appears.  We have only one word in our vocabulary, and hence,
  199. anything other than \*Qhello\*U generates an error.
  200. .cB
  201. % t
  202. bob
  203. invalid token near line 1 (text was 'b')
  204. invalid token near line 1 (text was 'o')
  205. invalid token near line 1 (text was 'b')
  206. invalid token near line 1 (text was '
  207. ')
  208. ^Dline 1: syntax error at "EOF" missing WORD
  209. % 
  210. .cE
  211. .LP
  212. The first \*Qinvalid token\*U errors are from the scanner, the last
  213. message is from the parser (function \f(CWa()\fP) indicating that
  214. end-of-file was found when a \f(CWWORD\fP was expected.  \f(CWEOF\fP
  215. was returned by the scanner because \f(CWbob\fP was ignored and
  216. end-of-file appeared immediately afterwards; \f(CWEOF\fP is a
  217. predefined token in any PCCTS vocabulary.
  218. .PP
  219. Adding more tokens to your language's vocabulary is easy\(emsimply add more
  220. \f(CW#token\fP definitions.  Consider this new example:
  221. .cB
  222. #token    "\e "     <<zzskip();>>            /* ignore blanks */
  223. #token    "\et"     <<zzskip();>>            /* ignore tabs */
  224. #token    "\en"     <<zzline++; zzskip();>>  /* ignore newlines */
  225. #token A  "apple"
  226. #token P  "pear"
  227. .cE
  228. .LP
  229. This example introduces lexical actions\(emactions that are executed
  230. upon recognition of a particular regular expression.  For most language
  231. descriptions, lexical actions are not used except to tell the scanner
  232. to skip a token or continue looking for more characters.
  233. \f(CWzzskip()\fP is a standard PCCTS function (generally, PCCTS
  234. variables/functions/defines are prefixed with \f(CWzz\fP to avoid name
  235. collisions with user variables) which forces the scanner to ignore the
  236. currently matched token and to try to find another.  Essentially, the
  237. first three token definitions here tell the scanner that it is to
  238. ignore white space, but to increment the current line number when it
  239. sees a newline.  The fourth and fifth definitions introduce two words
  240. into our vocabulary.  Notice that only the last two have labels
  241. associated with them.  Any \f(CW#token\fP instruction may give a
  242. label, but they are not necessary.  Labels are handy when you want an
  243. action to refer to the value (token number) of a particular token;
  244. also, when a regular expression is complicated or confusing, often it
  245. is better to use a label throughout your grammar rather than repeating
  246. the regular expression.  To illustrate this, we present the following
  247. four equivalent partial PCCTS descriptions:
  248. .IP \fI(i)\fP
  249. Repeated use of labels.
  250. .cB
  251. #token A "apple"
  252. #token P "pear"
  253.  
  254. a : A P
  255.   | P A
  256.   ;
  257. .cE
  258. .IP \fI(ii)\fP
  259. Repeated use of expressions.
  260. .cB
  261. #token "apple"
  262. #token "pear"
  263.  
  264. a : "apple" "pear"
  265.   | "pear" "apple"
  266.   ;
  267. .cE
  268. .IP \fI(iii)\fP
  269. Repeated use of implicitly-defined expressions.
  270. .cB
  271. a : "apple" "pear"
  272.   | "pear" "apple"
  273.   ;
  274. .cE
  275. .IP \fI(iv)\fP
  276. Mixed use of labels and expressions.
  277. .cB
  278. #token A  "apple"
  279. #token P  "pear"
  280.  
  281. a : "apple" P
  282.   | "pear" A
  283.   ;
  284. .cE
  285. .LP
  286. Each unique token regular-expression string in PCCTS gets its own token
  287. number.  Token labels are words that begin with a uppercase letter whereas
  288. rules begin with lowercase letters.  Repeating the same token string in a
  289. grammar merely refers to the same token; strings can only appear once in
  290. \f(CW#token\fP definitions, however, as this instruction attempts to define
  291. a new token.  An implicitly-defined token is one that is referenced but that
  292. has no formal \f(CW#token\fP instruction.  In fact, we use the
  293. \f(CW#token\fP only when the expression is long, when a lexical action must
  294. be attached, or when a label is required (so that a C action can refer
  295. to it).
  296. .PP
  297. Each rule \f(CWa\fP above indicates that either \f(CWapple\fP followed by
  298. \f(CWpear\fP is to be matched or \f(CWpear\fP followed by \f(CWapple\fP
  299. is to be matched.
  300. .PP
  301. Once again, let's test this vocabulary description with a complete,
  302. executable example:
  303. .cB
  304. #header <<#include "charbuf.h">>
  305.  
  306. <<main() { ANTLR(a(), stdin); }>>
  307.  
  308. #token    "\e "     <<zzskip();>>            /* ignore blanks */
  309. #token    "\et"     <<zzskip();>>            /* ignore tabs */
  310. #token    "\en"     <<zzline++; zzskip();>>  /* ignore newlines */
  311.  
  312. a : "apple" "pear"
  313.   | "pear" "apple"
  314.   ;
  315. .cE
  316. .LP
  317. To build the executable, we proceed as before:
  318. .cB
  319. % antlr -gk t.g
  320. Antlr parser generator   Version 1.06   1989-1992
  321. % dlg -i parser.dlg scan.c
  322. dlg  Version 1.0   1989, 1990, 1991
  323. % cc -g -I../h -o t t.c scan.c err.c
  324. .cE
  325. .LP
  326. To test the example, type:
  327. .cB
  328. % t
  329. apple
  330.      pear
  331. % 
  332. .cE
  333. No error is reported due to the validity of the input.  Note that the
  334. newline and the spaces were ignored because of the \f(CWzzskip()\fP actions
  335. associated with our token definitions for white space.  To ensure that
  336. \f(CWt\fP is actually doing something useful, try:
  337. .cB
  338. % t
  339. apple apple
  340. line 2: syntax error at "apple" missing pear
  341. ^D% 
  342. .cE
  343. .LP
  344. PCCTS generates parsers that automatically report errors and try to
  345. resynchronize the parser; hence, in this case, a control-D (\f(CW^D\fP) is
  346. necessary to terminate the program because \f(CWt\fP is looking for another
  347. token with which to resynchronize.  Because of the \f(CWzzline++\fP
  348. statement in the action for newline, the error is correctly reported on line
  349. 2.
  350. .PP
  351. The regular expressions used in the above examples are simple and do not use
  352. any of the \fImeta-characters\fP or regular expression operators.  Before
  353. presenting a more realistic example, we illustrate the use of some useful
  354. regular expression meta-characters (for a complete description see PCCTS
  355. documentation):
  356. .IP \f(CW@\fR
  357. \f(CWEOF\fP character
  358. .IP \f(CW\et\fR
  359. tab character
  360. .IP \f(CW\en\fR
  361. newline character
  362. .IP \f(CW\e\fP\fIc\fR
  363. character escape; used to obtain actual character for meta-characters
  364. .IP \f(CW(\fIe\f(CW)\fR
  365. keep expression \fIe\fP as an indivisible group
  366. .IP \f(CW[\fIc\f(CW]\fR
  367. match one character from list \fIc\fP
  368. .IP \f(CW[\fIx\f(CW-\fIy\f(CW]\fR
  369. match one character from range \fIx\fP to \fIy\fP
  370. .IP \f(CW~[\fIc\f(CW]\fR
  371. match one character not in list \fIc\fP
  372. .IP \f(CW{\fIe\f(CW}\fR
  373. expression \fIe\fP is optional
  374. .IP \fIe\f(CW*\fR
  375. match zero or more of \fIe\fP
  376. .IP \fIe\f(CW+\fR
  377. match one or more of \fIe\fP
  378. .IP \fIe\f(CW|\fIf\fR
  379. match either expression \fIe\fP \fBor\fR \fIf\fP
  380. .LP
  381. Naturally, the above operators and meta-characters can be used in many
  382. combinations to produce very complicated expressions.  To illustrate more
  383. complex expressions, we define the vocabulary of a calculator (ignoring
  384. white space for the moment).
  385. .cB
  386. #token NUM "[0-9]+"
  387. #token VAR "[a-zA-Z][a-zA-Z0-9]*"
  388. #token     "\e("
  389. #token     "\e)"
  390. #token     "\e+"
  391. #token     "\e-"
  392. #token     "\e*"
  393. #token     "/"
  394. .cE
  395. .LP
  396. A number is defined as a sequence of one or more decimal digits.
  397. Variables begin with an upper or lowercase letter, but can otherwise
  398. contain digits as well; note that \f(CW*\fP is used rather than
  399. \f(CW+\fP for variables because \f(CW+\fP would force \f(CWVAR\fP to
  400. recognize at least two characters.  This calculator has some tokens in
  401. its vocabulary that are identical to those of the regular expressions,
  402. so these must be escaped to tell the scanner to look for those actual
  403. characters.  To create an executable, we form a grammar which accepts
  404. one of the words in the vocabulary:
  405. .cB
  406. #header <<#include "charbuf.h">>
  407.  
  408. <<main() { ANTLR(a(), stdin); }>>
  409.  
  410. #token     "\e "     <<zzskip();>>            /* ignore blanks */
  411. #token     "\et"     <<zzskip();>>            /* ignore tabs */
  412. #token     "\en"     <<zzline++; zzskip();>>  /* ignore newlines */
  413. .cE
  414. .cB
  415. #token NUM "[0-9]+"
  416. #token VAR "[a-zA-Z][a-zA-Z0-9]*"
  417. #token     "\e("
  418. #token     "\e)"
  419. #token     "\e+"
  420. #token     "\e-"
  421. #token     "\e*"
  422. #token     "/"
  423.  
  424. a : NUM | VAR | "\e(" | "\e)" | "\e+" | "\e-" | "\e*" | "/" ;
  425. .cE
  426. .LP
  427. As before, we create the executable with (assuming the example is in
  428. \f(CWt.g\fR):
  429. .cB
  430. antlr -gk t.g
  431. dlg -i parser.dlg scan.c
  432. cc -g -I../h -o t t.c scan.c err.c
  433. .cE
  434. .LP
  435. The executable, \f(CWt\fP, will recognize any one token from our
  436. vocabulary.  The next section discusses how one employs rules to specify
  437. valid, structured sequences; i.e. how one defines the syntax of a language.
  438. .NH
  439. .iH Syntactic Analysis
  440. .PP
  441. The syntax of a language is the grammatical structure which summarizes
  442. the set of valid phrases in that language.  Because one cannot
  443. normally delineate all possible sentences, languages are described via
  444. a set of rules which obey the laws of a \fImeta-language\fP, which is
  445. literally a \*Qlanguage to describe languages\*U just as the syntax of
  446. regular expressions represents a language.  This section describes the
  447. format of a PCCTS language description\(emthe syntax of PCCTS rules
  448. and how they may be used to impose a structure upon a stream of input
  449. tokens.
  450. .PP
  451. The basic template used to build a grammar is:
  452. .nf
  453. .LP
  454.     \f(CW#header\fP \fIaction\fP
  455. .br
  456.     \fIaction(s)\fR and/or \f(CW#token\fR \fIdefinition(s)
  457. .br
  458.     rule(s)
  459. .br
  460.     action(s)\fR and/or \f(CW#token\fR \fIdefinition(s)
  461. .fi
  462. .LP
  463. To compile, all grammars must define a number of things inside the
  464. \f(CW#header\fP action; this instruction is not optional and must
  465. appear first in your file.  The rest of the file is basically a
  466. sequence of user actions, token and rule definitions\(emexcept that
  467. actions, not contained within rules, must be placed before or after
  468. the rule definitions.
  469. .PP
  470. Rules have the basic form:
  471. .cB
  472. \fIrule\fP: $alternative sub 1$ | $alternative sub 2$ | ... | $alternative sub n$ ;
  473. .cE
  474. .LP
  475. where $alternative sub i$ is a sequence of the following elements:
  476. .IP \fItoken\fP\ \ 
  477. Match \fItoken\fP on the input stream.
  478. .IP \fIrule\fP\ \ 
  479. Visit \fIrule\fP and match whatever is specified.
  480. .IP \fIaction\fR\ \ 
  481. Execute C \fIaction\fP.
  482. .IP "\f(CW($a sub 1$ | $a sub 2$ | ... | $a sub n$)\fR"
  483. Introduce a subrule\(emmatch one $a sub i$.
  484. .IP "\f(CW{$a sub 1$ | $a sub 2$ | ... | $a sub n$}\fR"
  485. Introduce an optional subrule; match one $a sub i$ or none.
  486. .IP "\f(CW($a sub 1$ | $a sub 2$ | ... | $a sub n$)*\fR"
  487. Conditionally match any sequence of $a sub i$'s.
  488. .IP "\f(CW($a sub 1$ | $a sub 2$ | ... | $a sub n$)+\fR"
  489. Match any sequence of $a sub i$'s.
  490. .LP
  491. Examples of rule definitions are:
  492. .cB
  493. w   :   WORD ("," WORD)*
  494.     ;
  495. .cE
  496. .LP
  497. where rule \f(CWw\fP matches a list of comma-separated \f(CWWORD\fP's.  The
  498. \f(CW("," WORD)*\fP construction says match zero or more \f(CW","\ WORD\fP
  499. sequences.  Consider,
  500. .cB
  501. st  :   "if" expr "then" st {"else" st} ";"
  502.     |   WORD ":=" expr
  503.     |    "begin" ( st ";" )+ "end"
  504.     ;
  505. .cE
  506. .LP
  507. where \f(CWexpr\fP is some rule that matches an arithmetic
  508. expression.  Rule \f(CWst\fP matches statements such as:
  509. .cB
  510. if $expr sub 1$ then begin
  511.   i := $expr sub 2$;
  512.   j := $expr sub 3$;
  513. end
  514. else
  515.   k := $expr sub 4$;
  516. .cE
  517. .LP
  518. The first alternative has an optional subrule that matches an
  519. \f(CWelse\fP-clause if it exists.  The third alternative matches one or more
  520. semicolon-delimited statements, which are enclosed in \f(CWbegin\fP and
  521. \f(CWend\fP.  Let's examine the description of a simple expression.
  522. .cB
  523. e   :   e1 ( ("\e+" | "\e-") e1 )*
  524.     ;
  525.  
  526. e1  :   WORD
  527.     |   INT
  528.     ;
  529. .cE
  530. .LP
  531. Rule \f(CWe\fP matches simple expressions with only plus and minus as
  532. operators; e.g. \f(CWa+3-b\fP or \f(CWa\fP.  Note that we have nested the
  533. \f(CW("\e+" | "\e-")\fP subrule within the \f(CW(...)*\fP subrule.
  534. .PP
  535. Let's build a complete PCCTS language description by extending the
  536. expression example.  Rules to handle multiplication and division will be
  537. added as well as token definitions to ignore white space etc...:
  538. .cB
  539. #header <<#include "charbuf.h">>
  540.  
  541. <<main() { ANTLR(calc(), stdin); }>>
  542.  
  543. #token     "[\e \et]"  <<zzskip();>>           /* ignore blanks, tabs */
  544. #token     "\en"      <<zzline++;>>           /* ignore newlines */
  545. #token INT "[0-9]+"
  546. #token FLOAT "[0-9]+ {. [0-9]+}"
  547.  
  548. calc:   ( e "\en" )* "@"
  549.     ;
  550.  
  551. e   :   e1 ( ("\e+" | "\e-") e1 )*
  552.     ;
  553.  
  554. e1  :   e2 ( ("\e*" | "/") e2 )*
  555.     ;
  556.  
  557. e2  :   INT
  558.     |    FLOAT
  559.     ;
  560. .cE
  561. .LP
  562. Note that newlines are no longer to be ignored, hence, the \f(CWzzskip()\fP
  563. function call has been removed from its lexical action.  Our language is a
  564. set of expressions terminated by newlines followed by end-of-file (\f(CW@\fP
  565. is a predefined lexical meta-symbol referring to end-of-file).  Without
  566. actions, testing this grammar is uninteresting because no output is
  567. generated (unless, of course, an invalid expression is given).  Therefore,
  568. let us place an action among the rule elements to generate some output.
  569. Augment rule \f(CWcalc\fP as follows:
  570. .cB
  571. calc:   ( e "\en" <<printf("found expression\en");>> )* "@"
  572.     ;
  573. .cE
  574. .LP
  575. Essentially, we have added C code to print out a brief message after an
  576. expression-newline pair has been encountered.  Create the executable,
  577. \f(CWt\fP, as before with:
  578. .cB
  579. antlr -gk t.g
  580. dlg -i parser.dlg scan.c
  581. cc -I../h -o t t.c scan.c err.c
  582. .cE
  583. .LP
  584.  
  585. Test the program via a few simple expressions:
  586. .cB
  587. % t
  588. 3+4*5
  589. found expression
  590. 3.15 / 6 - 2.1
  591. found expression
  592. ^D% 
  593. .cE
  594. .LP
  595. This example grammar is not recursive; i.e. no rule references another
  596. rule that directly or indirectly returns to itself.  But, recursion is
  597. a very powerful tool.  It allows the concept of
  598. \fIself-similarity\fP.  In other words, structures in which some
  599. subcomponents are similar to the outer structure.  Pascal has several
  600. self-similar constructs: record field definitions, procedure
  601. definitions, expressions, and type definitions to name a few.
  602. .PP
  603. To illustrate recursive grammars, we extend the above expression example to
  604. allow parenthesized subexpressions such as \f(CW(3+4)*7\fP.
  605. .cB
  606. e2  :   INT
  607.     |    FLOAT
  608.     |   "\e(" e "\e)"
  609.     ;
  610. .cE
  611. .LP
  612. Placing the subexpression construct at the lowest recursion level makes it
  613. have the highest precedence because of the nature of top-down, depth-first
  614. parsing.  To see this, consider the parse tree for \f(CW(3+4)*5\fP
  615. (beginning at rule \f(CWe\fP):
  616. .KS
  617. .PS
  618. .ps 11
  619. box invis "\f(CWe\fP" with .sw at (2.24,9.76) width 0.25 height 0.25
  620. box invis "\f(CWe2\fP" with .sw at (2.24,9.26) width 0.25 height 0.25
  621. box invis "\f(CWe3\fP" with .sw at (1.74,8.76) width 0.25 height 0.25
  622. box invis "\f(CW*\fP" with .sw at (2.24,8.76) width 0.25 height 0.25
  623. box invis "\f(CW5\fP" with .sw at (2.74,8.76) width 0.25 height 0.25
  624. box invis "\f(CWe\fP" with .sw at (1.74,8.26) width 0.25 height 0.25
  625. box invis "\f(CW(\fP" with .sw at (1.24,8.26) width 0.25 height 0.25
  626. box invis "\f(CW)\fP" with .sw at (2.24,8.26) width 0.25 height 0.25
  627. box invis "\f(CW3\fP" with .sw at (1.24,7.76) width 0.25 height 0.25
  628. box invis "\f(CW+\fP" with .sw at (1.74,7.76) width 0.25 height 0.25
  629. box invis "\f(CW4\fP" with .sw at (2.24,7.76) width 0.25 height 0.25
  630. line -> from 2.362,9.762 to 2.362,9.512
  631. line -> from 2.362,9.262 to 2.362,9.012
  632. line -> from 2.362,9.262 to 1.863,9.012
  633. line -> from 2.362,9.262 to 2.862,9.012
  634. line -> from 1.863,8.762 to 1.863,8.512
  635. line -> from 1.863,8.762 to 1.363,8.512
  636. line -> from 1.863,8.762 to 2.362,8.512
  637. line -> from 1.863,8.262 to 1.363,8.012
  638. line -> from 1.863,8.262 to 1.863,8.012
  639. line -> from 1.863,8.262 to 2.362,8.012
  640. .PE
  641. .KE
  642. .LP
  643. Clearly, \f(CW3+4\fP must be evaluated before the \f(CW*\fP for a valid
  644. result; this is precisely a depth-first evaluation of the parse tree (which
  645. PCCTS parsers do naturally).  The deeper the recursive nesting, the higher
  646. the precedence.  Extending the input expression to \f(CW(3+4)*(5-6)\fP
  647. yields:
  648. .KS
  649. .PS
  650. .ps 11
  651. box invis "\f(CWe3\fP" with .sw at (1.24,6.01) width 0.25 height 0.25
  652. box invis "\f(CWe\fP" with .sw at (1.24,5.51) width 0.25 height 0.25
  653. box invis "\f(CW(\fP" with .sw at (0.74,5.51) width 0.25 height 0.25
  654. box invis "\f(CW)\fP" with .sw at (1.74,5.51) width 0.25 height 0.25
  655. box invis "\f(CW3\fP" with .sw at (0.74,5.01) width 0.25 height 0.25
  656. box invis "\f(CW+\fP" with .sw at (1.24,5.01) width 0.25 height 0.25
  657. box invis "\f(CW4\fP" with .sw at (1.74,5.01) width 0.25 height 0.25
  658. line -> from 1.363,6.013 to 1.363,5.763
  659. line -> from 1.363,6.013 to 0.863,5.763
  660. line -> from 1.363,6.013 to 1.863,5.763
  661. line -> from 1.363,5.513 to 0.863,5.263
  662. line -> from 1.363,5.513 to 1.363,5.263
  663. line -> from 1.363,5.513 to 1.863,5.263
  664. box invis "\f(CWe3\fP" with .sw at (3.24,6.01) width 0.25 height 0.25
  665. box invis "\f(CWe\fP" with .sw at (3.24,5.51) width 0.25 height 0.25
  666. box invis "\f(CW(\fP" with .sw at (2.74,5.51) width 0.25 height 0.25
  667. box invis "\f(CW)\fP" with .sw at (3.74,5.51) width 0.25 height 0.25
  668. box invis "\f(CW5\fP" with .sw at (2.74,5.01) width 0.25 height 0.25
  669. box invis "\f(CW-\fP" with .sw at (3.24,5.01) width 0.25 height 0.25
  670. box invis "\f(CW6\fP" with .sw at (3.74,5.01) width 0.25 height 0.25
  671. line -> from 3.362,6.013 to 3.362,5.763
  672. line -> from 3.362,6.013 to 2.862,5.763
  673. line -> from 3.362,6.013 to 3.862,5.763
  674. line -> from 3.362,5.513 to 2.862,5.263
  675. line -> from 3.362,5.513 to 3.362,5.263
  676. line -> from 3.362,5.513 to 3.862,5.263
  677. box invis "\f(CWe\fP" with .sw at (2.24,7.01) width 0.25 height 0.25
  678. box invis "\f(CWe2\fP" with .sw at (2.24,6.51) width 0.25 height 0.25
  679. box invis "\f(CW*\fP" with .sw at (2.24,6.01) width 0.25 height 0.25
  680. line -> from 2.362,7.013 to 2.362,6.763
  681. line -> from 2.362,6.513 to 2.362,6.263
  682. line -> from 2.362,6.513 to 1.363,6.263
  683. line -> from 2.362,6.513 to 3.362,6.263
  684. .PE
  685. .KE
  686. .LP
  687. Again, both operands of the \f(CW*\fP must be evaluated before it can
  688. proceed.
  689. .PP
  690. As another example of recursive definitions, consider type definitions for a
  691. Pascal-like language.  Types look like:
  692. .cB
  693. char
  694. integer
  695. array [5] of char
  696. array [100] of array [20] of integer
  697. .cE
  698. .LP
  699. A grammar similar to the following could be used:
  700. .cB
  701. type:   "char"
  702.     |   "integer"
  703.     |   "array" "\e[" INT "\e]" "of" type
  704.     ;
  705. .cE
  706. The recursive invocation of \f(CWtype\fP by the \f(CWarray\fP alternative
  707. effectively allows chains of \f(CWarray\fP specifications.  The parse tree
  708. for
  709. .cB
  710. array [100] of array [20] of integer
  711. .cE
  712. .LP
  713. looks like:
  714. .KS
  715. .PS
  716. .ps 11
  717. box invis "\f(CW[\fP" with .sw at (2.49,8.76) width 0.25 height 0.25
  718. box invis "\f(CWarray\fP" with .sw at (1.99,8.76) width 0.25 height 0.25
  719. box invis "\f(CW20\fP" with .sw at (2.99,8.76) width 0.25 height 0.25
  720. box invis "\f(CW]\fP" with .sw at (3.49,8.76) width 0.25 height 0.25
  721. box invis "\f(CWof\fP" with .sw at (3.99,8.76) width 0.25 height 0.25
  722. box invis "\f(CWtype\fP" with .sw at (4.49,8.76) width 0.25 height 0.25
  723. line -> from 3.362,9.262 to 2.112,9.012
  724. line -> from 3.362,9.262 to 2.612,9.012
  725. line -> from 3.362,9.262 to 3.112,9.012
  726. line -> from 3.362,9.262 to 3.612,9.012
  727. line -> from 3.362,9.262 to 4.112,9.012
  728. line -> from 3.362,9.262 to 4.612,9.012
  729. box invis "\f(CWtype\fP" with .sw at (3.24,9.26) width 0.25 height 0.25
  730. box invis "\f(CW[\fP" with .sw at (1.24,9.26) width 0.25 height 0.25
  731. box invis "\f(CWarray\fP" with .sw at (0.74,9.26) width 0.25 height 0.25
  732. box invis "\f(CW100\fP" with .sw at (1.74,9.26) width 0.25 height 0.25
  733. box invis "\f(CW]\fP" with .sw at (2.24,9.26) width 0.25 height 0.25
  734. box invis "\f(CWof\fP" with .sw at (2.74,9.26) width 0.25 height 0.25
  735. box invis "\f(CWtype\fP" with .sw at (1.99,9.76) width 0.25 height 0.25
  736. line -> from 2.112,9.762 to 0.863,9.512
  737. line -> from 2.112,9.762 to 1.363,9.512
  738. line -> from 2.112,9.762 to 1.863,9.512
  739. line -> from 2.112,9.762 to 2.362,9.512
  740. line -> from 2.112,9.762 to 2.862,9.512
  741. line -> from 2.112,9.762 to 3.362,9.512
  742. box invis "\f(CWinteger\fP" with .sw at (4.49,8.26) width 0.25 height 0.25
  743. line -> from 4.612,8.762 to 4.612,8.512
  744. .PE
  745. .KE
  746. .LP
  747. In this case, we are less interested in precedence and more interested in
  748. allowing chains of array specifications.
  749. .PP
  750. In general, recursion and repetition constructs such as \f(CW(...)+\fP are
  751. needed to avoid delineating all possible phrases in a language.  Grammars
  752. are descriptions of the patterns found among the phrases of a particular
  753. language just as $size +2 SIGMA$ notation summarizes an infinite series.
  754. .PP
  755. The recognition of input languages, via the use of grammars, performs two
  756. tasks: it ensures phrase validity and directs translation to an output
  757. language.  The next section demonstrates how actions, embedded among the
  758. grammar elements, can be used to effect a translation.
  759. .NH
  760. .iH Translation
  761. .PP
  762. Given a grammar, PCCTS constructs a recognizer for phrases in that input
  763. language.  No translation from input to output is performed.  User actions
  764. must be supplied in the correct positions to generate output.  Translation
  765. occurs when an action produces output which is a function of the input
  766. phrase.  Actions have access to input phrase token values through an
  767. abstraction called an \fIattribute\fP.  These attributes are user-defined
  768. types and can be as simple as the text associated with a token.
  769. .PP
  770. This section introduces the notion of an attribute as a means of
  771. communicating with the lexical analyzer and presents a number of examples
  772. that explain how and where actions can be used to generate output.
  773. .NH 2
  774. .iH Attributes
  775. .PP
  776. Attributes are objects associated with all rules and rule elements,
  777. but we will only concern ourselves here with attributes associated
  778. with token and rule references.  Attributes are referenced in actions
  779. with the notation \f(CW\*d\fP$i$ where $i$ indicates that the
  780. attribute for the $i sup th$ token in that production is desired.
  781. Attributes are run-time objects and have no value until run-time.
  782. They are generally used to access the actual text (or a function of
  783. the text) of the tokens matched on the input stream.  The set of all
  784. tokens defines the \fIvocabulary\fP of the input language.  The term
  785. \*Qtoken\*U collectively refers to the token type (an integer that
  786. identifies it as part of the vocabulary) and the token text (the
  787. actual string that matched the regular expression for the token
  788. type).
  789. .PP
  790. Before illustrating attributes, we begin with an example.  The
  791. vocabulary of an input language (known a priori) may be the set {
  792. \f(CWWORD\fP, \f(CW"begin"\fP, \f(CWINT\fP }, which is the set of
  793. integer token types.  The text associated with a token type is only
  794. known at parser run-time because it depends on the input characters.
  795. Let us say that the grammatical structure of the language is any
  796. sequence of tokens in the vocabulary (ignoring white space); then, a
  797. valid sentence could be:
  798. .cB
  799. begin hello 34 13 bob
  800. .cE
  801. .LP
  802. The parser would see a token stream of tuples of the form (token type,
  803. token text):
  804. .cB
  805. (begin, begin)
  806. (WORD, hello)
  807. (INT, 34)
  808. (INT, 13)
  809. (WORD, bob)
  810. .cE
  811. .LP
  812. A different input sentence, with the same sequence of \fBtoken
  813. types\fP is:
  814. .cB
  815. begin hi 2 99 ptr
  816. .cE
  817. .LP
  818. which would yield the same sequence of token types, but a different
  819. set of token text:
  820. .cB
  821. (begin, begin)
  822. (WORD, hi)
  823. (INT, 2)
  824. (INT, 99)
  825. (WORD, ford)
  826. .cE
  827. The grammar might look like:
  828. .cB
  829. a : ( WORD | "begin" | INT )+
  830.   ;
  831. .cE
  832. .LP
  833. Only the token types are referenced in the grammar as they describe
  834. the structure of the language and are a shorthand notation for the set
  835. of valid input sentences.  Obviously, one could not delineate all
  836. possible sentences as there are infinitely many.  For a PCCTS
  837. description to perform a translation that is specific to the
  838. particular input, actions must access the text of the input tokens,
  839. not just the token type.  Attributes are provided to provide access to
  840. the text (or some function thereof) of an input token.  To illustrate
  841. this, we give a complete example and then, later, describe the
  842. particulars:
  843. .cB
  844. #header <<#include "charptr.h">>
  845.  
  846. <<main() { ANTLR(a(), stdin); }>>
  847.  
  848. #token "[\e \et]"        <<zzskip();>>
  849. #token "\en"            <<zzline++; zzskip();>>
  850.  
  851. a : ( WORD    <<printf(" %s", \*d1);>>
  852.     | "begin" <<printf(" begin");>>
  853.     | INT     <<printf(" %s", \*d1);>>
  854.     )+
  855.   ;
  856.  
  857. #token WORD "[a-z]+"
  858. #token INT  "[0-9]+"
  859. .cE
  860. .LP
  861. This example defines attributes to be strings representing what was
  862. found on the input stream and prints the stream of tokens back out.
  863. In other words, attributes are merely a copy of the words found; the
  864. mapping from token/lexeme to attribute is an identity mapping (do
  865. nothing but copy).  For the moment, concentrate on the actions.
  866. \f(CW\*d1\fP refers to the attribute of the first item in the
  867. production in which the action occurs; in this case, only one item
  868. appears per production.  Note that the action for the \f(CW"begin"\fP
  869. token does not need to refer to its attribute as it will always be
  870. \f(CWbegin\fP.  The rest of this section describes the particulars
  871. needed to understand everything else in the example.
  872. .PP
  873. PCCTS requires that the user define the data type or structure of the
  874. attributes as well as specify how to convert from lexemes to
  875. attributes.  The type is always defined by a C \f(CWtypedef\fP named
  876. \f(CWAttrib\fP and must be defined in the action associated with the
  877. \f(CW#header\fP instruction.  For example, if one wishes the attribute
  878. for a token to be simple integers, the following is a sufficient type
  879. definition:
  880. .cB
  881. #header <<typedef int Attrib;>>
  882. .cE
  883. .LP
  884. However, this does not tell PCCTS how to convert a token to an attribute.
  885. This is accomplished with a function called \f(CWzzcr_attr()\fP which defines
  886. the value of an attribute given complete information about a lexeme (token
  887. number and associated text).  It has the general form:
  888. .cB
  889. void
  890. zzcr_attr(a,token,text)
  891. Attrib *a;
  892. int token;
  893. char *text;
  894. {
  895.     /* *a = function(token, text); */
  896. }
  897. .cE
  898. where \f(CWa\fP points to an attribute created by PCCTS at run-time.  The
  899. user simply has to assign a value to \f(CW*a\fP.  In our case, we will use a
  900. macro version to set our attributes to the integer value of the input:
  901. .cB
  902. #define zzcr_attr(a,tok,txt) {*(a) = atoi(txt);}
  903. .cE
  904. .LP
  905. This specifies that whenever a token is matched on the input stream by
  906. the parser, an attribute of type \f(CWint\fP is to be created and
  907. assigned the result of \f(CWatoi(\fItext\f(CW)\fR where \fItext\fP is
  908. the character string matched for the token.  The attribute is then made
  909. available as \f(CW\*d\fP$i$ to actions in the production that matched
  910. the token.  For example,
  911. .cB
  912. #header <<
  913.     typedef int Attrib;
  914.     #define zzcr_attr(a,tok,txt) {*(a) = atoi(txt);}
  915. >>
  916.  
  917. <<main() { ANTLR(a(), stdin); }>>
  918.  
  919. #token "[\e \et]"        <<zzskip();>>
  920. #token "\en"            <<zzline++; zzskip();>>
  921.  
  922. a   :   "hi" "[0-9]+" <<printf("\*d1, \*d2 are %d, %d\en", \*d1, \*d2);>>
  923.     ;
  924. .cE
  925. .LP
  926. \f(CW\*d1\fP refers to the first token in the alternative,
  927. \f(CW"hi"\fR; similarly, \f(CW\*d2\fP refers to the the second token,
  928. \f(CW"[0-9]+"\fR.  When executed, the executable \f(CWt\fP (created as
  929. before) yields:
  930. .cB
  931. % t
  932. hi 34
  933. \*d1, \*d2 are 0, 34
  934. % 
  935. .cE
  936. .LP
  937. where \f(CWatoi()\fP of a non-numeric string is 0, but the text
  938. \f(CW34\fP gets converted to an integer (binary word) version of 34
  939. and printed back out as a number.
  940. .PP
  941. The token type can be tested to ensure that it is an integer before
  942. applying the \f(CWatoi()\fP function via:
  943. .cB
  944. #header <<
  945.     typedef int Attrib;
  946.     #define zzcr_attr(a,tok,txt) {if ( tok==INT ) *(a) = atoi(txt);}
  947. >>
  948. .cE
  949. .LP
  950. where \f(CWINT\fP is defined to be \f(CW"[0-9]+"\fR.  This defines an
  951. attribute for all \f(CWINT\fP tokens found on the input stream.  Other
  952. tokens have undefined attributes.
  953. .PP
  954. Attributes can have multiple elements or assume one of many values.  For
  955. example, we can extend the above example to handle \f(CWFLOAT\fP tokens as
  956. well:
  957. .cB
  958. #header <<typedef union { int ival; float fval; } Attrib;>>
  959. .cE
  960. .cB
  961. <<
  962. void
  963. zzcr_attr(a,token,text)
  964. Attrib *a;
  965. int token;
  966. char *text;
  967. {
  968.     switch ( token )
  969.     {
  970.         case INT   : (a)->ival = atoi(text); break;
  971.         case FLOAT : (a)->fval = atof(text); break;
  972.     }
  973. }
  974. >>
  975. .cE
  976. .LP
  977. The \f(CWtypedef\fP specifies that attributes are integer or floating
  978. point values.  When the regular expression for a floating point number
  979. (integer number) is matched on the input stream, \f(CWzzcr_attr()\fP
  980. converts the string of characters representing that number to a C
  981. \f(CWfloat\fP (\f(CWint\fP).
  982. .PP
  983. Attributes can become even more complicated, but typically, attributes
  984. are merely a copy of the text found on the input stream.  A standard
  985. PCCTS attribute definition is available as \f(CWcharbuf.h\fP and is
  986. defined as follows:
  987. .cB
  988. /* PCCTS attribute -- constant width text */
  989. #ifndef D_TextSize
  990. #define D_TextSize    30
  991. #endif
  992.  
  993. typedef struct { char text[D_TextSize]; } Attrib;
  994.  
  995. #define zzcr_attr(a,tok,t)    strncpy((a)->text, t, D_TextSize-1);
  996. .cE
  997. .LP
  998. These attributes are referred to by \f(CW\*d\fP$i$\f(CW.text\fP in actions.
  999. .PP
  1000. Each alternative begins a new sequence of \f(CW\*d\fP$i$'s and from an
  1001. enclosing scope/level, entire subules are counted as one unit.  This is best
  1002. explained with an example:
  1003. .cB
  1004. a   :   A B ( C D )+ E
  1005.     |   F G
  1006.     ;
  1007. .cE
  1008. .LP
  1009. From an action after token \f(CWE\fP, \f(CWA\fP is \f(CW\*d1\fP, \f(CWB\fP
  1010. is \f(CW\*d2\fP, the entire subrule \f(CW( C D )\fP is \f(CW\*d3\fP, and
  1011. \f(CWE\fP is \f(CW\*d4\fP; \f(CWC\fP and \f(CWD\fR are inaccessible from
  1012. outside the scope of the subrule.  From an action inside the subrule just
  1013. after the token \f(CWD\fP, \f(CWC\fP is \f(CW\*d1\fP and \f(CWD\fP is
  1014. \f(CW\*d2\fP.  In alternative two from an action after \f(CWG\fP, \f(CWF\fP
  1015. is \f(CW\*d1\fP and \f(CWF\fP is \f(CW\*d2\fP.  Attributes have a scoping
  1016. just like variables in a programming langauage.
  1017. .PP
  1018. Attributes are a means of communicating with the lexical analyzer.  Actions
  1019. may use these attributes to provide a translation.  The next section
  1020. utilizes the concepts presented here to build translators.
  1021. .NH 2
  1022. .iH Actions
  1023. .PP
  1024. Actions are rule elements just like token references, but perform a
  1025. different function.  Token references indicate that a particular token is to
  1026. be matched on the input stream at that point in the parse.  Actions indicate
  1027. that this action is to be performed at that point in the parse, immediately
  1028. following the preceding token match.  For example,
  1029. .cB
  1030. a   :   A <<$action sub 1$>> B ;
  1031.     |  ( C )+ <<$action sub 2$>>
  1032.     ;
  1033. .cE
  1034. .LP
  1035. $action sub 1$ is executed after the parser has found an \f(CWA\fP, but
  1036. before it has found a \f(CWB\fP.  $action sub 2$ is executed only after a
  1037. sequence of one or more \f(CWC\fP's has been found.
  1038. .PP
  1039. As a more concrete example, we augment the above \f(CWcalc\fP example to
  1040. print something more useful than \f(CWfound expression\fP:
  1041. .cB
  1042. calc:   ( e "\en" <<printf("\en");>> )* "@"
  1043.     ;
  1044.  
  1045. e   :   e1
  1046.         (   (  "\e+" <<printf(" add");>>
  1047.             |  "\e-" <<printf(" sub");>>
  1048.             )
  1049.             e1
  1050.         )*
  1051.     ;
  1052. .cE
  1053. .cB
  1054. e1  :   e2
  1055.         (   (  "\e*" <<printf(" mult");>>
  1056.             |  "/"   <<printf(" div");>>
  1057.             )
  1058.             e2
  1059.         )*
  1060.     ;
  1061.  
  1062. e2  :   INT     <<printf(" INT");>>
  1063.     |    FLOAT   <<printf(" FLOAT");>>
  1064.     ;
  1065. .cE
  1066. .LP
  1067. Essentially, we have added C code to print out the operand types and
  1068. operators.  Create the executable, \f(CWt\fP, as before with
  1069. .cB
  1070. antlr -gk t.g
  1071. dlg -i parser.dlg scan.c
  1072. cc -I../h -o t t.c scan.c err.c
  1073. .cE
  1074. .LP
  1075. Test the program via a few simple expressions:
  1076. .cB
  1077. % t
  1078. 3+4*5
  1079.  INT add INT mult INT
  1080. 3.15 / 6 - 2.1
  1081.  FLOAT div INT sub FLOAT
  1082. ^D% 
  1083. .cE
  1084. .LP
  1085. Now, let's use the attributes to generate code for a simple
  1086. \fIreverse-polish\fP stack machine whose operations are defined as follows:
  1087. .IP "\f(CWpush $opnd$\fR"
  1088. Push $opnd$ onto the stack.
  1089. .IP "\f(CWprint\fR"
  1090. Print the value of the top of stack; POP the value off the stack.
  1091. .IP "\f(CWadd\ \ \ \fR"
  1092. PUSH(POP + POP)
  1093. .IP "\f(CWsub\ \ \ \fR"
  1094. $a$ := POP
  1095. .br
  1096. $b$ := POP
  1097. .br
  1098. PUSH($b$ - $a$)
  1099. .IP "\f(CWmult\ \ \ \fR"
  1100. PUSH(POP * POP)
  1101. .IP "\f(CWdiv\ \ \ \fR"
  1102. $a$ := POP
  1103. .br
  1104. $b$ := POP
  1105. .br
  1106. PUSH($b$ / $a$)
  1107. .LP
  1108. Modify the rules as follows:
  1109. .cB
  1110. #header <<#include "charbuf.h">>
  1111.  
  1112. <<main() { ANTLR(calc(), stdin); }>>
  1113.  
  1114. #token     "[\e \et]"  <<zzskip();>>           /* ignore blanks, tabs */
  1115. #token     "\en"      <<zzline++;>>           /* ignore newlines */
  1116. #token INT "[0-9]+"
  1117. #token FLOAT "[0-9]+ {. [0-9]+}"
  1118. .cE
  1119. .cB
  1120. calc:   ( e "\en" <<printf("\etprint\en");>> )* "@"
  1121.     ;
  1122.  
  1123. e   :   <<char *op;>>
  1124.         e1
  1125.         (   (  "\e+" <<op="\etadd\en";>>
  1126.             |  "\e-" <<op="\etsub\en";>>
  1127.             )
  1128.             e1
  1129.             <<printf("%s", op);>>
  1130.         )*
  1131.     ;
  1132. .cE
  1133. .cB
  1134. e1  :   <<char *op;>>
  1135.         e2
  1136.         (   (  "\e*"  <<op="\etmult\en";>>
  1137.             |  "/"   <<op="\etdiv\en";>>
  1138.             )
  1139.             e2
  1140.             <<printf("%s", op);>>
  1141.         )*
  1142.     ;
  1143.  
  1144. e2  :   INT     <<printf("\etpush %s\en", \*d1.text);>>
  1145.     |    FLOAT   <<printf("\etpush %s\en", \*d1.text);>>
  1146.     ;
  1147. .cE
  1148. .LP
  1149. .bp
  1150. .EF ''''
  1151. .OF ''''
  1152. .LP
  1153. .PX
  1154.